Năm 1922, Heydrich gia nhập Hải quân Đức (Reichsmarine), tận dụng lợi thế về an ninh, cấu trúc và lương hưu của Hải quân. Ông trở thành một sĩ quan hải quân tại Kiel, quân cảng chính của Đức. Vào ngày 1 tháng 4 năm 1924, ông được thăng cấp lên Học viên Sĩ quan (Oberfähnrich zur See) và được gửi đi đào tạo sĩ quan tại Học viện Hải quân Mürwik.[17] Năm 1926, ông được thăng cấp bậc Thiếu úy (Leutnant zur See) và được chỉ định làm sĩ quan tín hiệu trên thiết giáp hạm SMS Schleswig-Holstein, soái hạm của Hạm đội Biển Bắc của Đức. Sau khi được thăng cấp bậc, ông dần dần nhận được sự thừa nhận từ nhiều người hơn. Ông đã nhận được lời khen ngợi từ cấp trên nhưng đã có xích mích với một số thuyền viên khác. Vào ngày 1 tháng 7 năm 1928, ông đã được thăng lên cấp bậc trung úy (Oberleutnant zur See). Quân hàm ngày càng lớn đã thúc đẩy tham vọng cũng như sự kiêu ngạo của Heydrich.[18]

Heydrich cũng đã trở nên khét tiếng với vô số mối tình của mình. Vào tháng 12 năm 1930, khi tham dự một buổi khiêu vũ của một câu lạc bộ chèo thuyền, ông đã làm quen với Lina von Osten. Hai người đã dần dần có tình cảm với nhau và đã sớm đính hôn. Lina vốn là một đảng viên Đảng Quốc xã. Bà đã tham dự buổi họp đảng đầu tiên của mình vào năm 1929.[19] Đầu năm 1931, Heydrich bị buộc tội là "đã làm những chuyện không thích hợp với tư cách của một sĩ quan và một người đàn ông" vì đã cắt đứt hôn ước. Heydrich vốn trước đó đã có hôn ước với một người phụ nữ khác 6 tháng trước khi ông quen đính hôn với Lina.[20] Đô đốc Erich Raeder vì thế đã trục xuất Heydrich ra khỏi hải quân vào tháng 4 năm đó. Heydrich sau đó đã nhận được một khoản tiền trợ cấp thôi việc là 200 Reichsmark (tương đương 640€ theo giá năm 2009) mỗi tháng trong vòng hai năm tiếp đó.[21] Vào tháng 12 năm 1931, Heydrich đã kết hôn với Lina von Osten.[22]